#define _CRT_SECURE_NO_WARNINGS 1
#include"sort.h"
// 希尔排序
//void ShellSort(int* a, int n)
//{
//	int gap = n;
//	while (gap > 1)
//	{
//		gap = (gap / 3) + 1;
//	}
//	//一组一组来
//	/*for (int j = 0; j < gap; j++) 
//	{
//		for (int i = j; i < n - gap; i += gap)
//		{
//			int end = i;
//			int tmp = a[end + gap];
//			while (end >= 0)
//			{
//				if (tmp < a[end])
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			a[end + gap] = tmp;
//		}
//	}*/
//	//多组并着走
//	for (int i = 0; i < n - gap; ++i)
//	{
//		int end = i;
//		int tmp = a[end + gap];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + gap] = a[end];
//				end -= gap;
//			}
//			else
//			{
//				break;
//			}
//		}
//		a[end + gap] = tmp;
//	}
//}
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
// 选择排序
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
			
		}
		Swap(&a[begin], &a[mini]);
        if(maxi == begin)
        {
            maxi = mini;
        }
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

	
Print(int* a, int m)
{
	for (int i = 0; i < m; i++)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	/*int a[] = { 9,6,4,1,3,7,3,8,9,1 };*/
	int a[] = { 3,6,4,1,9,7,2,4,5,8 };
	//ShellSort(a,sizeof(a)/sizeof(int));
	SelectSort(a, sizeof(a) / sizeof(int));
	Print(a, sizeof(a) / sizeof(int));
	return 0;
}
